◀ Prev · Parts · Full · Next ▶

The class of problems for which both YES and NO-instances are allowed to be identified with some error is called BPP. This class acts as the randomized equivalent of P, i.e. BPP represents the class of efficient randomized algorithms.

Quicksort was discovered by Tony Hoare in 1959, and subsequently published in 1961.cite-ref-4[4] In the same year, Hoare published the quickselect algorithm,cite-ref-5[5] which finds the median element of a list in linear expected time. It remained open until 1973 whether a deterministic linear-time algorithm existed.cite-ref-6[6]

◀ Prev · Parts · Full · Next ▶